/**
 * Created with IntelliJ IDEA.
 * User: final-work
 * Date: 04.04.13
 * Time: 13:51
 * To change this template use File | Settings | File Templates.
 */
import java.util.*;


public class Teilsumme {


    public static int maxTeilsumme3(List<Integer> zahlenfolge) {
            int teilsumme_max = Integer.MIN_VALUE;
            int index_von = 0;
            int index_bis = 0;

            int zahlenfolge_size = zahlenfolge.size();

        List<List> result = new ArrayList<List>();

        for (int i = 0; i < zahlenfolge_size; i++) {
           // teilsumme_max = Integer.MIN_VALUE;
            for (int j = i; j < zahlenfolge_size; j++) {

                int temp_max_value = 0;

                List<Integer> maxFolgeList = new ArrayList<Integer>();
                for (int k = i; k < j; k++) {
                    temp_max_value += zahlenfolge.get(k);
                    maxFolgeList.add(zahlenfolge.get(k));

                    if (temp_max_value > teilsumme_max) {
                        teilsumme_max = temp_max_value;
                        List temp_res = new ArrayList();
                        index_von = i;
                        index_bis = j;

                        temp_res.add(temp_max_value);
                        temp_res.add(index_von);
                        temp_res.add(index_bis);
                        temp_res.add(maxFolgeList);

                        result.add(temp_res);

                        System.out.println("max summe : "+teilsumme_max+" von : "+ index_von +" bis : "+ index_bis);
                    }

                }

            }

        }
        System.out.println(result.toString());
        return teilsumme_max;
    }

    public static int maxTeilsumme2(int[] zahlenfolge) {
        int zahlenfolge_size = zahlenfolge.length;
        int teilsumme_max = Integer.MIN_VALUE;

        int[][] matrix_teilsumme = new int[zahlenfolge_size][zahlenfolge_size];

        for (int j = 0; j < zahlenfolge_size; j++) {
            int temp_zwischenergebnis = 0;

            for (int k = j; k < zahlenfolge_size; k++) {
                temp_zwischenergebnis += zahlenfolge[j] + zahlenfolge[k];
                matrix_teilsumme[j][k] = temp_zwischenergebnis;
                System.out.print(matrix_teilsumme[j][k]);
            }
        }


        int result = Integer.MIN_VALUE;

        // zweiten geschachtelten Schleife
        for (int i = 0; i < matrix_teilsumme.length; i++) {			//die suchung an alle stelle des Matrix für beste lösung
            for (int j = 0; j < matrix_teilsumme.length; j++) {
                int tmp = matrix_teilsumme[i][j];
                if(tmp > teilsumme_max){
                    teilsumme_max = tmp;
                  //  index_von = i;
                  //  index_bis = i + j;
            }
        }


    }
        System.out.println("maxteilsumme2 :" + teilsumme_max);
        return teilsumme_max;
    }


    public static void main(String[] args) {
        List<Integer> test = new ArrayList<Integer>();
        test.add(1);
        test.add(2);
        test.add(3);
        test.add(4);
        test.add(5);


        int test1 []  = {5,-8,3,3,-5,7,-2,-7,3,5};

        maxTeilsumme3(test);

    }
}
